#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个下标从 0 开始的 m x n 二进制矩阵 mat 和一个整数 cols ，表示你需要选出的列数。

如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行 被覆盖 了。

请你返回在选择 cols 列的情况下，被覆盖 的行数 最大 为多少。



示例 1：



输入：mat = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], cols = 2
输出：3
解释：
如上图所示，覆盖 3 行的一种可行办法是选择第 0 和第 2 列。
可以看出，不存在大于 3 行被覆盖的方案，所以我们返回 3 。
 * */
//组合数 需要回溯的 回溯+ 选中对应列 然后判断(写一个方法)

//

bool inIT(vector<int> & cols,int temp)
{
    for (int i = 0; i <cols.size() ; ++i) {

        if (temp==cols[i])
            return true;

    }
    return false;

}

int checkMax(vector<vector<int>>& mat,vector<int> & cols)
{
    int maxV=0;
    int row=mat.size();
    int col=mat[0].size();


    for (int i = 0; i <row ; ++i) {

        int flat= 0;
        for (int j = 0; j <col ; ++j) {
            if (inIT(cols,j))
                continue;
            if (mat[i][j]==1)
            {
                flat=1;
                break;
            }


        }

        if (flat==0)
            maxV++;


    }
    

    return maxV;
}


//排列组合
vector<int> teee;
int maxV=0;
void maximumRows_t(vector<vector<int>>& mat, int colsChoose,int start) {

    int row=mat.size();
    int col=mat[0].size();

    if (teee.size()>colsChoose)
        return;
    if (teee.size()==colsChoose)
    {
       maxV= max(maxV,checkMax(mat,teee)) ;
        return;
    }


    for (int i = start; i <col ; ++i) {
        teee.push_back(i);
        maximumRows_t(mat,colsChoose,i+1);
        teee.pop_back();
    }





}



int maximumRows(vector<vector<int>>& mat, int cols) {

    maximumRows_t(mat,cols,0);
    return maxV;

}